package com.ljy.my_study.leetcode.四数之和;

import java.util.*;

/**
 * @author lijunying
 * @date 2021/5/18 9:38
 */
public class TestMain {

//    给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
//
//    注意：答案中不可以包含重复的四元组。
//
//             
//
//    示例 1：
//
//    输入：nums = [1,0,-1,0,-2,2], target = 0
//    输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
//    示例 2：
//
//    输入：nums = [], target = 0
//    输出：[]
//             
//
//    提示：
//
//            0 <= nums.length <= 200
//            -109 <= nums[i] <= 109
//            -109 <= target <= 109
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/4sum
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


    public static void main(String[] args) {

    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(nums==null||nums.length<4){
            return null;
        }
        Arrays.sort(nums);
        int len=nums.length;
        Map<Integer,List<List<Integer>>> map=new HashMap<>();
        for(int i=2;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                int key=nums[i]+nums[j];
                List<List<Integer>> list=map.getOrDefault(key,new ArrayList<>());
                list.add(new ArrayList<Integer>(Arrays.asList(i,j)));
                map.put(key,list);
            }
        }
        List<List<Integer>> result=new ArrayList<>();
        for(int i=0;i<len-3;i++){
            for(int j=i+1;j<len-2;j++){
                int key=target-nums[i]-nums[j];
                if(map.containsKey(key)){
                    List<List<Integer>> list=map.get(key);
                    for(List<Integer> subList:list){
                        if(subList.get(0)>j){
                            result.add(Arrays.asList(nums[i],nums[j],nums[subList.get(0)],nums[subList.get(1)]));
                        }
                    }
                }
            }
        }
        return result;
    }
}
